// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_LOOP_ANALYSIS_H_
#define V8_COMPILER_LOOP_ANALYSIS_H_

#include "src/base/iterator.h"
#include "src/compiler/graph.h"
#include "src/compiler/node.h"
#include "src/globals.h"
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {
    namespace compiler {

        // TODO(titzer): don't assume entry edges have a particular index.
        static const int kAssumedLoopEntryIndex = 0; // assume loops are entered here.

        class LoopFinderImpl;

        using NodeRange = base::iterator_range<Node**>;

        // Represents a tree of loops in a graph.
        class LoopTree : public ZoneObject {
        public:
            LoopTree(size_t num_nodes, Zone* zone)
                : zone_(zone)
                , outer_loops_(zone)
                , all_loops_(zone)
                , node_to_loop_num_(static_cast<int>(num_nodes), -1, zone)
                , loop_nodes_(zone)
            {
            }

            // Represents a loop in the tree of loops, including the header nodes,
            // the body, and any nested loops.
            class Loop {
            public:
                Loop* parent() const { return parent_; }
                const ZoneVector<Loop*>& children() const { return children_; }
                size_t HeaderSize() const { return body_start_ - header_start_; }
                size_t BodySize() const { return exits_start_ - body_start_; }
                size_t ExitsSize() const { return exits_end_ - exits_start_; }
                size_t TotalSize() const { return exits_end_ - header_start_; }
                size_t depth() const { return static_cast<size_t>(depth_); }

            private:
                friend class LoopTree;
                friend class LoopFinderImpl;

                explicit Loop(Zone* zone)
                    : parent_(nullptr)
                    , depth_(0)
                    , children_(zone)
                    , header_start_(-1)
                    , body_start_(-1)
                    , exits_start_(-1)
                    , exits_end_(-1)
                {
                }
                Loop* parent_;
                int depth_;
                ZoneVector<Loop*> children_;
                int header_start_;
                int body_start_;
                int exits_start_;
                int exits_end_;
            };

            // Return the innermost nested loop, if any, that contains {node}.
            Loop* ContainingLoop(Node* node)
            {
                if (node->id() >= node_to_loop_num_.size())
                    return nullptr;
                int num = node_to_loop_num_[node->id()];
                return num > 0 ? &all_loops_[num - 1] : nullptr;
            }

            // Check if the {loop} contains the {node}, either directly or by containing
            // a nested loop that contains {node}.
            bool Contains(Loop* loop, Node* node)
            {
                for (Loop* c = ContainingLoop(node); c != nullptr; c = c->parent_) {
                    if (c == loop)
                        return true;
                }
                return false;
            }

            // Return the list of outer loops.
            const ZoneVector<Loop*>& outer_loops() const { return outer_loops_; }

            // Return the unique loop number for a given loop. Loop numbers start at {1}.
            int LoopNum(Loop* loop) const
            {
                return 1 + static_cast<int>(loop - &all_loops_[0]);
            }

            // Return a range which can iterate over the header nodes of {loop}.
            NodeRange HeaderNodes(Loop* loop)
            {
                return NodeRange(&loop_nodes_[0] + loop->header_start_,
                    &loop_nodes_[0] + loop->body_start_);
            }

            // Return the header control node for a loop.
            Node* HeaderNode(Loop* loop);

            // Return a range which can iterate over the body nodes of {loop}.
            NodeRange BodyNodes(Loop* loop)
            {
                return NodeRange(&loop_nodes_[0] + loop->body_start_,
                    &loop_nodes_[0] + loop->exits_start_);
            }

            // Return a range which can iterate over the body nodes of {loop}.
            NodeRange ExitNodes(Loop* loop)
            {
                return NodeRange(&loop_nodes_[0] + loop->exits_start_,
                    &loop_nodes_[0] + loop->exits_end_);
            }

            // Return a range which can iterate over the nodes of {loop}.
            NodeRange LoopNodes(Loop* loop)
            {
                return NodeRange(&loop_nodes_[0] + loop->header_start_,
                    &loop_nodes_[0] + loop->exits_end_);
            }

            // Return the node that represents the control, i.e. the loop node itself.
            Node* GetLoopControl(Loop* loop)
            {
                // TODO(turbofan): make the loop control node always first?
                for (Node* node : HeaderNodes(loop)) {
                    if (node->opcode() == IrOpcode::kLoop)
                        return node;
                }
                UNREACHABLE();
            }

            Zone* zone() const { return zone_; }

        private:
            friend class LoopFinderImpl;

            Loop* NewLoop()
            {
                all_loops_.push_back(Loop(zone_));
                Loop* result = &all_loops_.back();
                return result;
            }

            void SetParent(Loop* parent, Loop* child)
            {
                if (parent != nullptr) {
                    parent->children_.push_back(child);
                    child->parent_ = parent;
                    child->depth_ = parent->depth_ + 1;
                } else {
                    outer_loops_.push_back(child);
                }
            }

            Zone* zone_;
            ZoneVector<Loop*> outer_loops_;
            ZoneVector<Loop> all_loops_;
            ZoneVector<int> node_to_loop_num_;
            ZoneVector<Node*> loop_nodes_;
        };

        class V8_EXPORT_PRIVATE LoopFinder {
        public:
            // Build a loop tree for the entire graph.
            static LoopTree* BuildLoopTree(Graph* graph, Zone* temp_zone);
        };

    } // namespace compiler
} // namespace internal
} // namespace v8

#endif // V8_COMPILER_LOOP_ANALYSIS_H_
